#include <fstream>  // 用于文件操作
#include <iostream> // 用于输入输出
#include <sstream>  // 用于字符串流处理
#include <stack>    // 用于栈数据结构
#include <string>   // 用于字符串操作

using namespace std;

// 用于确定操作符的优先级
int precedence(char op) {
    if (op == '+' || op == '-') return 1;  // 加减的优先级最低
    if (op == '*' || op == '/') return 2;  // 乘除的优先级较高
    return 0;  // 其他字符不具有优先级
}

// 打印字符栈的内容，显示当前栈的状态（自定义的调试函数）
void print_stack(stack<char> operators) {
    stack<char> operators2;  // 创建一个临时栈用于保存顺序
    // 将原栈的内容倒入临时栈
    while (!operators.empty()) {
        operators2.push(operators.top());
        operators.pop();
    }
    cout << "栈目前是这样的,栈底在冒号旁边：";
    // 打印栈内容
    while (!operators2.empty()) {
        cout << operators2.top() << ' ';
        operators2.pop();
    }
    cout << endl;
}

// 打印整数栈的内容，显示当前栈的状态（自定义的调试函数）
void print_stack_i(stack<int> operators) {
    stack<int> operators2;  // 创建一个临时栈用于保存顺序
    // 将原栈的内容倒入临时栈
    while (!operators.empty()) {
        operators2.push(operators.top());
        operators.pop();
    }
    cout << "栈目前是这样的,栈底在冒号旁边：";
    // 打印栈内容
    while (!operators2.empty()) {
        cout << operators2.top() << ' ';
        operators2.pop();
    }
    cout << endl;
}

// 将中缀表达式转换为后缀表达式
string p_to_m(string expression) {
    stack<char> operators;  // 用于存放操作符
    string res;  // 用于存放最终的后缀表达式

    // 遍历中缀表达式中的每个字符
    for (char &i : expression) {
        if (i == '#') {
            continue;  // 忽略"#"符号
        }
        if (isdigit(i)) {
            res += i;  // 如果是数字，直接添加到结果字符串
        } else if (i == '(') {
            operators.push(i);  // 如果是左括号，入栈
            print_stack(operators);
        } else if (i == ')') {
            // 如果是右括号，弹出栈中所有操作符直到遇到左括号
            while (!operators.empty() && operators.top() != '(') {
                res += ' ';
                res += operators.top();
                operators.pop();
                print_stack(operators);
            }
            if (!operators.empty()) {
                operators.pop();  // 弹出左括号
                print_stack(operators);
            }
        } else {  // 处理操作符
            res += ' ';  // 在操作符前加空格
            // 弹出优先级大于等于当前操作符的操作符
            while (!operators.empty() &&
                   precedence(operators.top()) >= precedence(i)) {
                res += operators.top();
                res += ' ';
                operators.pop();
                print_stack(operators);
            }
            operators.push(i);  // 当前操作符入栈
            print_stack(operators);
        }
    }

    // 清空栈中剩余的操作符
    while (!operators.empty()) {
        if (operators.top() != '(') {
            res += ' ';
            res += operators.top();
        }
        operators.pop();
        print_stack(operators);
    }
    res = "# " + res + " #";  // 在结果的首尾添加"#"作为标记
    return res;
}

// 计算后缀表达式的值
int mycal_string(string res1) {
    stringstream ss(res1);  // 用字符串流处理后缀表达式
    string it;  // 用于暂存从流中提取的每个元素
    stack<int> mycal;  // 栈用于存储操作数

    // 遍历后缀表达式中的每个元素
    while (ss >> it) {
        if (it == "#") {
            continue;  // 忽略"#"符号
        } else if (isdigit(it[0])) {
            mycal.push(stoi(it));  // 将数字字符串转换为整数并压入栈
            print_stack_i(mycal);  // 打印当前栈状态
        } else {
            // 如果是操作符，从栈中弹出两个操作数
            int operand2 = mycal.top();
            mycal.pop();
            int operand1 = mycal.top();
            mycal.pop();
            print_stack_i(mycal);

            int result;

            // 根据操作符计算结果
            switch (it[0]) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    result = operand1 / operand2;
                    break;
            }
            mycal.push(result);    // 将结果压入栈
            print_stack_i(mycal);  // 打印当前栈状态
        }
    }

    return mycal.top();  // 栈顶元素即为最终结果
}

int main() {
    // 从文件中读取中缀表达式
    ifstream file("exp.txt");
    string expression;
    if (file.is_open()) {
        getline(file, expression);  // 读取一行中缀表达式
        file.close();
    } else {
        cout << "前缀表达式的txt文件打开失败。";
        return 0;
    }
    cout << "中缀表达式为:";
    cout << expression << endl << endl;

    // 转换为后缀表达式
    stack<char> operators;
    string res;
    res = p_to_m(expression);  // 中缀转后缀
    cout << "后缀表达式为:";
    cout << res << endl;

    // 将后缀表达式写入文件
    ofstream file_out;
    file_out.open("output.txt");
    file_out << res;

    // 使用后缀表达式计算结果
    cout << "\n使用后缀表达式计算：\n";
    int res2 = mycal_string(res);
    cout << "最后结果为：" << res2 << endl;
}

